package com.acwing.partition12;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2022/1/25 17:17
 */
public class AC1175最大半连通子图 {

    private static final int N = 100010, M = 2000010, INF = 0x3f3f3f3f, P = 13331;
    private static int[] h = new int[N], hs = new int[N], e = new int[M], ne = new int[M];

    private static int n = 0, m = 0, x = 0, idx = 0, cnt = 0, timestamp = 0;
    private static Deque<Integer> stk = new ArrayDeque<>(N);
    private static boolean[] inStk = new boolean[N];
    private static int[] scc = new int[N], size = new int[N], dfn = new int[N], low = new int[N];
    //dp[i]表示以连通分量i为终点的最长链最大节点数量之和，sum[i]表示转移成最大的方案数
    private static int[] dp = new int[N], sum = new int[N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        x = Integer.parseInt(s[2]);
        for (int i = 0; i < N; i++) h[i] = hs[i] = -1;
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int a = Integer.parseInt(s[0]), b = Integer.parseInt(s[1]);
            add(h, a, b);
        }
        //tarjan算法寻找连通分量
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) tarjan(i);
        }
        //根据连通分量建立新图
        Set<Integer> set = new HashSet<>();
        for (int u = 1; u <= n; u++) {
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i], a = scc[u], b = scc[v], hash = a * P + b;
                if (a != b && !set.contains(hash)) {
                    add(hs, a, b);
                    set.add(hash);
                }
            }
        }
        //节点编号递减的顺序一定是拓扑序，以每一个点为起点做一遍动态规划，记录能达到的最远路径和对应的方案数
        for (int u = cnt; u > 0; u--) {
            if (dp[u] == 0) {
                //当前点没有被更新过，必然是起点
                dp[u] = size[u];
                sum[u] = 1;
            }
            for (int i = hs[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (dp[v] < dp[u] + size[v]) {
                    dp[v] = dp[u] + size[v];
                    sum[v] = sum[u];
                } else if (dp[v] == dp[u] + size[v]) {
                    sum[v] = (sum[u] + sum[v]) % x;
                }
            }
        }
        //最后统计一下以哪个点为终点的长链的点的数目最多，将他所携带的点的数目和最长链数量找出来
        int max = 0, ans = 0;
        for (int i = 1; i <= cnt; i++) {
            if (dp[i] > max) {
                max = dp[i];
                ans = sum[i];
            } else if (dp[i] == max) {
                ans = (ans + sum[i]) % x;
            }
        }
        writer.write(String.format("%d\n%d\n", max, ans));
        writer.flush();
    }

    private static void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        stk.addLast(u);
        inStk[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStk[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            cnt++;
            int v = -1;
            do {
                v = stk.pollLast();
                inStk[v] = false;
                scc[v] = cnt;
                size[cnt]++;
            } while (u != v);
        }
    }

    private static void add(int[] h, int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}
